1. Field of the Invention
The present invention relates to a method and an apparatus for detecting straight line information with the Hough transform, which are capable of reducing overhead of voting computation and also increasing hourly throughput, by selectively performing voting computation according to the Hough transform only with respect to certain pixels, and calculating votes of the rest pixels using the votes of the neighborhood pixels.
2. Description of the Prior Art
FIG. 1 illustrates a process of mapping respective pixels present in (x, y) coordinate space of an image into (r, θ) coordinate space according to the conventional Hough transform scheme.
Referring to FIG. 1, the respective pixels present in the (x,y) coordinate space of the image are mapped into (r,θ) coordinate space referred to as Hough space, and straight line information is detected based on (r,θ) of the intercepts with frequency above a threshold.
To be specific, the respective pixels in the (x,y) coordinate space of the image as illustrated in FIG. 1 are mapped into curves in the (r,θ) coordinate space, while the pixels present on the same straight line in the (x,y) coordinate space have the intercepts in the (r,θ) coordinate space. Accordingly, through the Hough transform as the one illustrated in FIG. 1, the accumulated frequencies of a specific (r,θ) coordinate space can be viewed as the number of pixels present on the same straight line, and (r,θ) values at the intercepts with frequencies above threshold can be defined as the straight line components. The (r,θ) value computed according to Mathematical Expression 1 below can be defined to be the votes, and the process of accumulating the frequencies of the computed votes in the two-dimensional (2D) alignment in the (r,θ) coordinate space is referred to as the ‘voting’.x·cos θ+y·sin θ=r  [Mathematical Expression 1]
The voting process involves standardization of 2D alignment θ and obtaining corresponding votes. The voting process thus computes corresponding votes per unit Δθ according to the resolution of the θ standardization, and repeats the process by θ/Δθ=n total. That is, when K is the total number of input pixels to detect straight line components, the time complexity to perform voting process of the Hough transform is expressed as O(Kn). The overhead of Mathematical Expression 1 has a relatively higher time complexity (O(Kn)), which in turn greatly affects the system performance. Accordingly, it is necessary to provide ways to reduce the overhead of Mathematical Expression 1 to meet real time performance requirement for the Hough transform.